{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Image Overlap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestOverlap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #图像重叠"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个图像 <code>img1</code> 和 <code>img2</code> ，两个图像的大小都是 <code>n x n</code> ，用大小相同的二进制正方形矩阵表示。二进制矩阵仅由若干 <code>0</code> 和若干 <code>1</code> 组成。</p>\n",
    "\n",
    "<p><strong>转换</strong> 其中一个图像，将所有的 <code>1</code> 向左，右，上，或下滑动任何数量的单位；然后把它放在另一个图像的上面。该转换的 <strong>重叠</strong> 是指两个图像 <strong>都</strong> 具有 <code>1</code> 的位置的数目。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>请注意，转换 <strong>不包括</strong> 向任何方向旋转。越过矩阵边界的 <code>1</code> 都将被清除。</p>\n",
    "\n",
    "<p>最大可能的重叠数量是多少？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/09/overlap1.jpg\" style=\"width: 450px; height: 231px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>将 img1 向右移动 1 个单位，再向下移动 1 个单位。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/09/overlap_step1.jpg\" style=\"width: 450px; height: 105px;\" />\n",
    "两个图像都具有 <code>1</code> 的位置的数目是 3（用红色标识）。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/09/overlap_step2.jpg\" style=\"width: 450px; height: 231px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>img1 = [[1]], img2 = [[1]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>img1 = [[0]], img2 = [[0]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == img1.length == img1[i].length</code></li>\n",
    "\t<li><code>n == img2.length == img2[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 30</code></li>\n",
    "\t<li><code>img1[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "\t<li><code>img2[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [image-overlap](https://leetcode.cn/problems/image-overlap/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [image-overlap](https://leetcode.cn/problems/image-overlap/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0],[0,1,0],[0,1,0]]\\n[[0,0,0],[0,1,1],[0,0,1]]', '[[1]]\\n[[1]]', '[[0]]\\n[[0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        ans = 0\n",
    "        for x in range(1-n, n):\n",
    "            for y in range(1-n, n):\n",
    "                temp = 0\n",
    "                for i in range(n):\n",
    "                    for j in range(n):\n",
    "                        if img1[i][j] and 0 <= i + x < n and 0 <= j + y < n and img2[i + x][j + y]:\n",
    "                            temp += 1\n",
    "                ans = max(temp, ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n=len(img1)\n",
    "        def overlap(dx,dy):\n",
    "            res=0\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    if (0<=x+dx<n and 0<=y+dy<n and img1[x][y]+img2[x+dx][y+dy]==2):\n",
    "                        res+=1\n",
    "            return res\n",
    "        res=0\n",
    "        for dx in range(-n+1,n):\n",
    "            for dy in range(-n+1,n):\n",
    "                cnt=overlap(dx,dy)\n",
    "                res=max(res,cnt)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        res = 0\n",
    "        for a in range(-n, n):\n",
    "            for b in range(-n, n):\n",
    "                count = 0\n",
    "                for i in range(n):\n",
    "                    if i + a < n and i + a >= 0:\n",
    "                        for j in range(n):\n",
    "                            if j + b < n and j + b >= 0:\n",
    "                                if img1[i][j] == 1 and img2[a + i][b + j] == 1:\n",
    "                                    count += 1\n",
    "                res = max(count, res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        def overlap(dx,dy):\n",
    "            cnt=0\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    if 0<=x+dx<n and 0<=y+dy<n and img1[x][y]+img2[x+dx][y+dy]==2:\n",
    "                        cnt+=1\n",
    "            return cnt\n",
    "        n=len(img1)\n",
    "        res=0\n",
    "        for dx in range(1-n,n):\n",
    "            for dy in range(1-n,n):\n",
    "                cnt=overlap(dx,dy)\n",
    "                res=max(cnt,res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        f1 = [0] * n\n",
    "        f2 = [0] * n\n",
    "        MASK = (1 << n) - 1\n",
    "\n",
    "        for i, (row1, row2) in enumerate(zip(img1, img2)):\n",
    "            num = 0\n",
    "            for x in reversed(row1):\n",
    "                num = (num << 1) + x\n",
    "            f1[i] = num\n",
    "            num = 0\n",
    "            for x in reversed(row2):\n",
    "                num = (num << 1) + x\n",
    "            f2[i] = num\n",
    "        \n",
    "        ans = 0\n",
    "        for dx in range(-n, n+1):\n",
    "            for dy in range(-n, n+1):\n",
    "                cnt = 0\n",
    "                if dx >= 0:\n",
    "                    for a, b in zip(f1, f2[dx:]):\n",
    "                        cnt += (a << (-dy) & MASK & b).bit_count() if dy < 0 else (a >> dy & b).bit_count()\n",
    "                else:\n",
    "                    for a, b in zip(f1[-dx:], f2):\n",
    "                        cnt += (a << (-dy) & MASK & b).bit_count() if dy < 0 else (a >> dy & b).bit_count()\n",
    "                ans = max(cnt, ans)\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        ans = 0\n",
    "        for x in range(1-n, n):\n",
    "            for y in range(1-n, n):\n",
    "                temp = 0\n",
    "                for i in range(max(-x, 0), min(n-x, n)):\n",
    "                    for j in range(max(-y, 0), min(n-y, n)):\n",
    "                        if img1[i][j] and img2[i + x][j + y]:\n",
    "                            temp += 1\n",
    "                ans = max(temp, ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        N = len(img1)\n",
    "        check = []\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                if img2[i][j]:\n",
    "                    check.append((i, j))\n",
    "        ans = 0\n",
    "        for row_shift in range(-N + 1, N):\n",
    "            for col_shift in range(-N + 1, N):\n",
    "                cur = 0\n",
    "                for i, j in check:\n",
    "                    if 0 <= row_shift + i < N and 0 <= col_shift + j < N and img1[row_shift + i][col_shift + j]:\n",
    "                        cur += 1\n",
    "                if cur > ans:\n",
    "                    ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(\n",
    "        self, \n",
    "        img1: List[List[int]],\n",
    "        img2: List[List[int]]\n",
    "    ) -> int:\n",
    "                       \n",
    "        def overlap(dx: int,dy: int) -> int:\n",
    "            res = 0\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    if (0 <= x + dx < n and \n",
    "                        0 <= y + dy < n and\n",
    "                        img1[x][y] + img2[x + dx][y + dy] == 2):\n",
    "                        res += 1\n",
    "            return res\n",
    "        \n",
    "\n",
    "        n = len(img1)\n",
    "\n",
    "        res = 0\n",
    "        \n",
    "        for dx in range(-n + 1, n):\n",
    "            for dy in range(-n + 1, n):\n",
    "                cnt = overlap(dx, dy)\n",
    "                res = max(res, cnt)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        # 把img2固定不动，枚举img1移动的方向\n",
    "        # 定义(dx, dy)表示把img1向下移动dx，向右移动dy，如果是负数表示相反的方向，比如dx=1表示向下移动1位，那么-1就是向上移动1位\n",
    "        # 可以知道，为了img1和img2有交集，dx的范围为[-n + 1, n - 1],同理dy也一样\n",
    "        # 设（i,j）为img2的某个点，那么img1移动（dx, dy）以后和（i,j）重合的点在img1上的坐标就是（i - dx, j - dy）\n",
    "        # 以dx举例，画个图就好理解，在img1坐标i - dx 移动dx以后刚好是i，同理dy\n",
    "        # 当然所有点都要在合理的区间[0, n - 1]\n",
    "        n = len(img1)\n",
    "        ans = 0\n",
    "        for dx in range(-n + 1, n):\n",
    "            for dy in range(-n + 1, n):\n",
    "                s = 0\n",
    "                # 优化一下i和j的枚举\n",
    "                for i in range(min(n, n + dx)):\n",
    "                    for j in range(min(n, n + dy)):\n",
    "                        if 0 <= i - dx < n and 0 <= j - dy < n:\n",
    "                            if img2[i][j] == 1 and img1[i - dx][j - dy] == 1:\n",
    "                                s += 1\n",
    "                ans = max(ans, s)\n",
    "        return ans          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        # 把img2固定不动，枚举img1移动的方向\n",
    "        # 定义(dx, dy)表示把img1向下移动dx，向右移动dy，如果是负数表示相反的方向，比如dx=1表示向下移动1位，那么-1就是向上移动1位\n",
    "        # 可以知道，为了img1和img2有交集，dx的范围为[-n + 1, n - 1],同理dy也一样\n",
    "        # 设（i,j）为img2的某个点，那么img1移动（dx, dy）以后和（i,j）重合的点在img1上的坐标就是（i - dx, j - dy）\n",
    "        # 以dx举例，画个图就好理解，在img1坐标i - dx 移动dx以后刚好是i，同理dy\n",
    "        # 当然所有点都要在合理的区间[0, n - 1]\n",
    "        n = len(img1)\n",
    "        ans = 0\n",
    "        for dx in range(-n + 1, n):\n",
    "            for dy in range(-n + 1, n):\n",
    "                s = 0\n",
    "                # 优化一下i和j的枚举\n",
    "                for i in range(max(0, dx),min(n, n + dx)):\n",
    "                    for j in range(max(0, dy),min(n, n + dy)):\n",
    "                        # if 0 <= i - dx < n and 0 <= j - dy < n:\n",
    "                        if img2[i][j] == 1 and img1[i - dx][j - dy] == 1:\n",
    "                            s += 1\n",
    "                ans = max(ans, s)\n",
    "        return ans          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n=len(img1)\n",
    "        ans=a=b=c=d=0\n",
    "        \n",
    "        for k in range(n):\n",
    "            for p in range(n):\n",
    "                for i in range(n):\n",
    "                    for j in range(n):\n",
    "                        if i+k<n and j+p<n and img1[i+k][j+p]==img2[i][j] and img2[i][j]==1:\n",
    "                            a+=1\n",
    "                        if i>=k and j+p<n and img1[i-k][j+p]==img2[i][j] and img2[i][j]==1:\n",
    "                            b+=1\n",
    "                        if j>=p and i+k<n and img1[i+k][j-p]==img2[i][j] and img2[i][j]==1:\n",
    "                            c+=1\n",
    "                        if j>=p and i>=k and img1[i-k][j-p]==img2[i][j] and img2[i][j]==1:\n",
    "                            d+=1\n",
    "                ans=max(ans,a,b,c,d)\n",
    "                a=b=c=d=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "\n",
    "        def get(i, j):\n",
    "            return img2[i][j] if 0 <= i < n and 0 <= j < n else 0\n",
    "\n",
    "        def count(i, j):\n",
    "            cnt = 0\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    if img1[x][y] and get(x + i, y + j):\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(-n + 1, n):\n",
    "            for j in range(-n + 1, n):\n",
    "                ans = max(ans, count(i, j))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n=len(img1)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                #right\n",
    "                t=0\n",
    "                for oi in range(n):\n",
    "                    for oj in range(n):\n",
    "                        ni,nj=oi+i,oj+j \n",
    "                        if 0<=ni<n and 0<=nj<n:\n",
    "                            t+=img1[ni-i][nj-j]&img2[ni][nj]\n",
    "              \n",
    "                ans=max(ans,t)\n",
    "                #left\n",
    "                t=0\n",
    "                for oi in range(n):\n",
    "                    for oj in range(n):\n",
    "                        ni,nj=oi+i,oj-j \n",
    "                        if 0<=ni<n and 0<=nj<n:\n",
    "                            t+=img1[ni-i][nj+j]&img2[ni][nj]\n",
    "                ans=max(ans,t)\n",
    "                #up\n",
    "                t=0\n",
    "                for oi in range(n):\n",
    "                    for oj in range(n):\n",
    "                        ni,nj=oi-i,oj+j \n",
    "                        if 0<=ni<n and 0<=nj<n:\n",
    "                            t+=img1[ni+i][nj-j]&img2[ni][nj]\n",
    "              \n",
    "                ans=max(ans,t)\n",
    "                #down\n",
    "                t=0\n",
    "                for oi in range(n):\n",
    "                    for oj in range(n):\n",
    "                        ni,nj=oi-i,oj-j \n",
    "                        if 0<=ni<n and 0<=nj<n:\n",
    "                            t+=img1[ni+i][nj+j]&img2[ni][nj]\n",
    "                ans=max(ans,t)\n",
    "               \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\r\n",
    "        n = len(img1)\r\n",
    "        def solve(m1, m2, lx, ly):\r\n",
    "            res = 0 \r\n",
    "            for i in range(lx):\r\n",
    "                for j in range(ly):\r\n",
    "                    res += m1[i][j] == 1 and m2[n - lx + i][n - ly + j] == 1 \r\n",
    "            return res \r\n",
    "        def solve2(m1, m2, lx, ly):\r\n",
    "            res = 0 \r\n",
    "            for i in range(lx):\r\n",
    "                for j in range(n - ly, n):\r\n",
    "                    res += m1[i][j] == 1 and m2[i + n - lx][j - n + ly] == 1\r\n",
    "            return res \r\n",
    "        ans = 0 \r\n",
    "        for lx in range(1, n + 1):\r\n",
    "            for ly in range(1, n + 1):\r\n",
    "                ans = max(ans, solve(img1, img2, lx, ly))\r\n",
    "                ans = max(ans, solve(img2, img1, lx, ly))\r\n",
    "                ans = max(ans, solve2(img1, img2, lx, ly))\r\n",
    "                ans = max(ans, solve2(img2, img1, lx, ly))\r\n",
    "        return ans \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(\n",
    "        self, \n",
    "        img1: List[List[int]], \n",
    "        img2: List[List[int]]\n",
    "    ) -> int:\n",
    "        n = len(img1)\n",
    "\n",
    "        def overlap(dx: int, dy: int) -> int:\n",
    "            cnt = 0\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n and 0 <= ny < n:\n",
    "                        cnt += img1[x][y] + img2[nx][ny] == 2\n",
    "\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for dx in range(-n + 1, n):\n",
    "            for dy in range(-n + 1, n):\n",
    "                cnt = overlap(dx, dy)\n",
    "                res = max(res, cnt)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n=len(img1)\n",
    "        \n",
    "        def transfer(x,y):\n",
    "            img=copy.deepcopy(img1)\n",
    "            newlist=[]\n",
    "            if x>=0:\n",
    "                newlist=[[0]*n for _ in range(x)]\n",
    "                newlist.extend(img[0:n-x])\n",
    "            else:\n",
    "                newlist.extend(img[-x:])\n",
    "                newlist.extend([[0]*n for _ in range(-x)])\n",
    "            if y>=0:\n",
    "                for row in newlist:\n",
    "                    for _ in range(y):\n",
    "                        row.insert(0,0)\n",
    "                        row.pop()\n",
    "            else:\n",
    "                for row in newlist:\n",
    "                    for _ in range(-y):\n",
    "                        row.append(0)\n",
    "                        row.pop(0)\n",
    "            \n",
    "            return newlist\n",
    "        \n",
    "        def check(newimg):\n",
    "            return sum(1 for i in range(n) for j in range(n) if newimg[i][j]==img2[i][j]==1)\n",
    "        \n",
    "        return max(check(transfer(x,y)) for x in range(1-n,n) for y in range(1-n,n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        # 把img2固定不动，枚举img1移动的方向\n",
    "        # 定义(dx, dy)表示把img1向下移动dx，向右移动dy，如果是负数表示相反的方向，比如dx=1表示向下移动1位，那么-1就是向上移动1位\n",
    "        # 可以知道，为了img1和img2有交集，dx的范围为[-n + 1, n - 1],同理dy也一样\n",
    "        # 设（i,j）为img2的某个点，那么img1移动（dx, dy）以后和（i,j）重合的点在img1上的坐标就是（i - dx, j - dy）\n",
    "        # 以dx举例，画个图就好理解，在img1坐标i - dx 移动dx以后刚好是i，同理dy\n",
    "        # 当然所有点都要在合理的区间[0, n - 1]\n",
    "        n = len(img1)\n",
    "        ans = 0\n",
    "        for dx in range(-n + 1, n):\n",
    "            for dy in range(-n + 1, n):\n",
    "                s = 0\n",
    "                for i in range(n):\n",
    "                    for j in range(n):\n",
    "                        if 0 <= i - dx < n and 0 <= j - dy < n:\n",
    "                            if img2[i][j] == 1 and img1[i - dx][j - dy] == 1:\n",
    "                                s += 1\n",
    "                ans = max(ans, s)\n",
    "        return ans          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        def juanji(im1,im2,a,b): #往右下移动，如果im1，im2反转就是左上\n",
    "            m= len(im1)\n",
    "            res = 0\n",
    "            for i in range(n-a):\n",
    "                for j in range(n-b):\n",
    "                    res += im1[i+a][j+b]*im2[i][j]\n",
    "            return res\n",
    "        def juanji2(im1,im2,a,b):#左下移动 比如左1下0 a=0，b=1\n",
    "            m= len(im1)\n",
    "            res = 0\n",
    "            for i in range(n-a):#i从0到2\n",
    "                for j in range(n-b):#j从0到1\n",
    "                    res += im1[i][j+b]*im2[i+a][j]\n",
    "            return res\n",
    "\n",
    "        n= len(img1)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans = max(ans,juanji(img1,img2,i,j))\n",
    "                ans = max(ans,juanji(img2,img1,i,j))\n",
    "                ans = max(ans,juanji2(img1,img2,i,j))\n",
    "                ans = max(ans,juanji2(img2,img1,i,j))\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestOverlap(self, A, B):\n",
    "        N = len(A)\n",
    "        A2 = [complex(r, c) for r, row in enumerate(A)\n",
    "              for c, v in enumerate(row) if v]\n",
    "        B2 = [complex(r, c) for r, row in enumerate(B)\n",
    "              for c, v in enumerate(row) if v]\n",
    "        Bset = set(B2)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        for a in A2:\n",
    "            for b in B2:\n",
    "                d = b-a\n",
    "                if d not in seen:\n",
    "                    seen.add(d)\n",
    "                    ans = max(ans, sum(x+d in Bset for x in A2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        # 这里计算一个图像经过（向上，向右）或者（向上，向左）与另一个图像的重叠度\n",
    "        def slove(img1: List[List[int]], img2: List[List[int]])->int:\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    # 深拷贝img1\n",
    "                    imgs = [g.copy() for g in img1]\n",
    "                    t = 0\n",
    "                    for p in range(n-1,-1,-1):\n",
    "                        for k in range(n-1,-1,-1):\n",
    "                            if p-i<0 or k-j<0:\n",
    "                                imgs[p][k] = 0\n",
    "                            else:\n",
    "                                imgs[p][k] = imgs[p-i][k-j]\n",
    "                            if imgs[p][k] and img2[p][k]:\n",
    "                                t+=1\n",
    "                    res = max(res,t)\n",
    "                    # 这里必须重置一下\n",
    "                    imgs = [g.copy() for g in img1]\n",
    "                    t = 0\n",
    "                    for p in range(n-1,-1,-1):\n",
    "                        for k in range(n):\n",
    "                            if p-i<0 or k+j>=n:\n",
    "                                imgs[p][k] = 0\n",
    "                            else:\n",
    "                                imgs[p][k] = imgs[p-i][k+j]\n",
    "                            if imgs[p][k] and img2[p][k]:\n",
    "                                t+=1\n",
    "                    res = max(res,t)\n",
    "            return res\n",
    "        # 一个正向，一个反向\n",
    "        return max(slove(img1,img2),slove(img2,img1))\n",
    "                            \n",
    "s = Solution()\n",
    "s.largestOverlap([[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestOverlap(self, A, B):\n",
    "        N = len(A)\n",
    "        count = collections.Counter()\n",
    "        for i, row in enumerate(A):\n",
    "            for j, v in enumerate(row):\n",
    "                if v:\n",
    "                    for i2, row2 in enumerate(B):\n",
    "                        for j2, v2 in enumerate(row2):\n",
    "                            if v2:\n",
    "                                count[i-i2, j-j2] += 1\n",
    "        return max(count.values() or [0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "\n",
    "        def slove(img1: List[List[int]], img2: List[List[int]])->int:\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    imgs = [g.copy() for g in img1]\n",
    "                    t = 0\n",
    "                    for p in range(n-1,-1,-1):\n",
    "                        for k in range(n-1,-1,-1):\n",
    "                            if p-i<0 or k-j<0:\n",
    "                                imgs[p][k] = 0\n",
    "                            else:\n",
    "                                imgs[p][k] = imgs[p-i][k-j]\n",
    "                            if imgs[p][k] and img2[p][k]:\n",
    "                                t+=1\n",
    "                    res = max(res,t)\n",
    "                    imgs = [g.copy() for g in img1]\n",
    "                    t = 0\n",
    "                    for p in range(n-1,-1,-1):\n",
    "                        for k in range(n):\n",
    "                            if p-i<0 or k+j>=n:\n",
    "                                imgs[p][k] = 0\n",
    "                            else:\n",
    "                                imgs[p][k] = imgs[p-i][k+j]\n",
    "                            if imgs[p][k] and img2[p][k]:\n",
    "                                t+=1\n",
    "                    res = max(res,t)\n",
    "            return res\n",
    "        return max(slove(img1,img2),slove(img2,img1))\n",
    "                            \n",
    "s = Solution()\n",
    "s.largestOverlap([[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        pos1 = {str(r) + \"_\" + str(c): 1 for r in range(len(img1)) for c in range(len(img1[0])) if img1[r][c] == 1}\n",
    "        pos2 = {str(r) + \"_\" + str(c): 1 for r in range(len(img2)) for c in range(len(img2[0])) if img2[r][c] == 1}\n",
    "\n",
    "        count = 0\n",
    "        delta = dict()\n",
    "        for it1 in pos1.keys():\n",
    "            r1, c1 = [int(i) for i in it1.split(\"_\")]\n",
    "\n",
    "            for it2 in pos2.keys():\n",
    "                r2, c2 = [int(i) for i in it2.split(\"_\")]\n",
    "\n",
    "                delta_r = r2 - r1\n",
    "                delta_c = c2 - c1\n",
    "                key = str(delta_r) + \"_\" + str(delta_c)\n",
    "                if key in delta:\n",
    "                    continue\n",
    "\n",
    "                delta[key] = 0\n",
    "                for it3 in pos1.keys():\n",
    "                    r3, c3 = [int(i) for i in it3.split(\"_\")]\n",
    "                    \n",
    "                    if str(r3 + delta_r) + \"_\" + str(c3 + delta_c) in pos2:\n",
    "                        delta[key] += 1\n",
    "\n",
    "                count = max(count, delta[key])\n",
    "\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        cnt = collections.defaultdict(int)\n",
    "\n",
    "        for i, row in enumerate(img1):\n",
    "            for j, v in enumerate(row):\n",
    "                if v:\n",
    "                    for k, row2 in enumerate(img2):\n",
    "                        for l, v2 in enumerate(row2):\n",
    "                            if v2:\n",
    "                                cnt[i -k, j - l] += 1\n",
    "        \n",
    "\n",
    "        return max(cnt.values(), default = 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        record = defaultdict(int)\n",
    "        n = len(img1)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img1[i][j] == 1:\n",
    "                    for x in range(n):\n",
    "                        for y in range(n):\n",
    "                            if img2[x][y] == 1:\n",
    "                                record[(i-x,j-y)] += 1\n",
    "                                if record[(i-x,j-y)]>res:\n",
    "                                    res = record[(i-x,j-y)]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "\n",
    "        ones_img1 = [(i, j) for i in range(n) for j in range(n) if img1[i][j] == 1]\n",
    "        ones_img2 = [(i, j) for i in range(n) for j in range(n) if img2[i][j] == 1]\n",
    "\n",
    "        translations = Counter((i2 - i1, j2 - j1) for (i1, j1) in ones_img1 for (i2, j2) in ones_img2)\n",
    "\n",
    "        return max(translations.values(), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        nrow = len(img1)\n",
    "        dic1 = []\n",
    "        dic2 = []\n",
    "        for i in range(nrow):\n",
    "            for j in range(nrow):\n",
    "                if img1[i][j] == 1:\n",
    "                    dic1.append([i,j])\n",
    "                if img2[i][j] == 1:\n",
    "                    dic2.append([i,j])\n",
    "\n",
    "        if len(dic1) == 0 or len(dic2) == 0:\n",
    "            return(0)\n",
    "            \n",
    "        dic1_new = dic1\n",
    "        dic2_new = dic2\n",
    "        dic1_new = set([f'{i}_{j}' for [i,j] in dic1_new])\n",
    "        dic2_new = set([f'{i}_{j}' for [i,j] in dic2_new])\n",
    "        res = len(dic1_new & dic2_new)\n",
    "                    \n",
    "        directions1 = [[1,0],[-1,0],[0,0]]\n",
    "        directions2 = [[0,1],[0,-1],[0,0]]\n",
    "\n",
    "        for direction1 in directions1:\n",
    "            for direction2 in directions2:\n",
    "                if not (direction1 == [0,0] and direction2 == [0,0]):\n",
    "                    for step1 in range(1,nrow):\n",
    "                        for step2 in range(1,nrow):\n",
    "                            dir_i = direction1[0]*step1+direction2[0]*step2\n",
    "                            dir_j = direction1[1]*step1+direction2[1]*step2\n",
    "                            \n",
    "                            dic1_new = []\n",
    "                            for [i,j] in dic1:\n",
    "                                dic1_new.append(f'{i+dir_i}_{j+dir_j}')\n",
    "                            dic1_new = set(dic1_new)\n",
    "                            res = max([res, len(dic1_new & dic2_new)])\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        cnt = defaultdict(int)\n",
    "        one = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img1[i][j]:\n",
    "                    one.append([i, j])\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img2[i][j]:\n",
    "                    for a, b in one:\n",
    "                        cnt[(i - a, j - b)] += 1\n",
    "        return max(cnt.values()) if cnt else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        di = dict()\n",
    "        for i1 in range(len(img1)):\n",
    "            for j1 in range(len(img1[i1])):\n",
    "                if img1[i1][j1]:\n",
    "                    for i2 in range(len(img2)):\n",
    "                        for j2 in range(len(img2[i2])):\n",
    "                            if img2[i2][j2]:\n",
    "                                di[(i1 - i2, j1- j2)] = di.get((i1 - i2, j1 - j2), 0) + 1\n",
    "        return max(di.values()) if di else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestOverlap(self, A, B):\n",
    "        N = len(A)\n",
    "        count = collections.Counter()\n",
    "        for i, row in enumerate(A):\n",
    "            for j, v in enumerate(row):\n",
    "                if v:\n",
    "                    for i2, row2 in enumerate(B):\n",
    "                        for j2, v2 in enumerate(row2):\n",
    "                            if v2:\n",
    "                                count[i-i2, j-j2] += 1\n",
    "        return max(count.values() or [0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestOverlap(self, A, B):\n",
    "        N = len(A)\n",
    "        count = collections.Counter()\n",
    "        for i, row in enumerate(A):\n",
    "            for j, v in enumerate(row):\n",
    "                if v:\n",
    "                    for i2, row2 in enumerate(B):\n",
    "                        for j2, v2 in enumerate(row2):\n",
    "                            if v2:\n",
    "                                count[i-i2, j-j2] += 1\n",
    "        return max(count.values() or [0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        one = []\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img1[i][j]:\n",
    "                    one.append([i, j])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img2[i][j]:\n",
    "                    for x, y in one:\n",
    "                        cnt[(i-x, j-y)] += 1\n",
    "        return max(cnt.values()) if cnt else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        cnt = defaultdict(int)\n",
    "        one = []\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img1[i][j]:\n",
    "                    one.append([i, j])\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img2[i][j]:\n",
    "                    for x, y in one:\n",
    "                        cnt[(i-x, j-y)] += 1\n",
    "        return max(cnt.values()) if cnt else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\n",
    "        n = len(img1)\n",
    "        cnt = defaultdict(int)\n",
    "        one = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img1[i][j]:\n",
    "                    one.append([i, j])\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if img2[i][j]:\n",
    "                    for a, b in one:\n",
    "                        cnt[(i - a, j - b)] += 1\n",
    "        return max(cnt.values()) if cnt else 0\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/image-overlap/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:\r\n",
    "        counter={}\r\n",
    "        for r1,row1 in enumerate(img1):\r\n",
    "            for c1,v1 in enumerate(row1):\r\n",
    "                if v1==0:\r\n",
    "                    continue\r\n",
    "                for r2,row2 in enumerate(img2):\r\n",
    "                    for c2,v2 in enumerate(row2):\r\n",
    "                        if v2==0:\r\n",
    "                            continue\r\n",
    "                        dif=(r2-r1,c2-c1)\r\n",
    "                        counter[dif]=counter.get(dif,0)+1\r\n",
    "        return max(counter.values(),default=0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
